public class Text7 {
    // 分割回文串
    // 这里有个语法疏漏--》substring方法切割字符串是从【j，i）！！！
    public boolean isF(String s) {
        for (int i = 0; i < s.length() / 2 ; i++) {
            if (s.charAt(i) == s.charAt(s.length() - i - 1))
                continue;
            return false;
        }

        return true;
    }

    public int minCut (String s) {
        // write code here
        int size = s.length();

        // 字符串前i个字符的最小切割数
        int[] dp = new int[size + 1];

        for (int i = 0; i <= size; ++i) {
            dp[i] = i - 1;
        }

        for (int i = 1; i <= size; i++) {
            for (int j = 0; j < i; j++) {

                if (isF(s.substring(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[size];
    }
}
